<!doctype html>
<html>

<head>
    <meta charset='utf-8'>
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/github-markdown-css/2.4.1/github-markdown.min.css">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.11.0/styles/default.min.css">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.8.3/katex.min.css">
    <link rel="stylesheet" href="https://gitcdn.xyz/repo/goessner/mdmath/master/css/texmath.css">
    <link rel="stylesheet" href="https://gitcdn.xyz/repo/goessner/mdmath/master/css/vscode-texmath.css">

</head>

<body class="markdown-body">
    <h1 data-line="0" class="code-line code-line" id="2">作业2: 黑白棋游戏 实验报告</h1>
    <p data-line="2" class="code-line code-line">
        <strong>吴政亿 151220129
            <a href="mailto:18805156360@163.com">18805156360@163.com</a>
        </strong>
        <br> (南京大学 计算机科学与技术系, 南京 210093)</p>
    <p data-line="5" class="code-line code-line">
        <strong>摘要</strong>：介绍MiniMax搜索的实现；应用AlphaBeta剪枝并比较速度；理解heuristic函数并改进；阅读并理解MTDDecider类并与MiniMaxDecider类比较异同
        <br>
        <strong>关键词</strong>：MiniMax搜索，AlphaBeta剪枝，heuristic函数，MTD(f)算法</p>
    <h2 data-line="7" class="code-line code-line" id="task-1">Task 1</h2>
    <p data-line="9" class="code-line code-line">
        <code>MiniMaxDecider.java</code>的代码相比于书本中的样例，将min与max进行了合并，用一个
        <code>boolean maximize</code>代替，以及通过+1,-1将两个函数抽象成一个，下面对三个函数进行简要介绍。</p>
    <h3 data-line="11" class="code-line code-line" id="">变量定义</h3>
    <table>
        <thead>
            <tr>
                <th>类型</th>
                <th>变量名</th>
                <th>意义</th>
            </tr>
        </thead>
        <tbody>
            <tr>
                <td>boolean</td>
                <td>maximize</td>
                <td>为true时最大化val,为false时最小化val</td>
            </tr>
            <tr>
                <td>int</td>
                <td>depth</td>
                <td>限制了递归的深度</td>
            </tr>
            <tr>
                <td>Map</td>
                <td>computedStates</td>
                <td>用Hash存储不同局面及得分，避免重复运算</td>
            </tr>
        </tbody>
    </table>
    <h3 data-line="19" class="code-line code-line" id="minimaxdeciderboolean-maximize--int-depth">MiniMaxDecider(boolean maximize, int depth)</h3>
    <p data-line="21" class="code-line code-line">对上面的变量进行初始化</p>
    <h3 data-line="23" class="code-line code-line" id="public-action-decidestate-state">public Action decide(State state)</h3>
    <ol>
        <li data-line="25" class="code-line code-line">根据maximize将value初始化为负无穷或正无穷</li>
        <li data-line="26" class="code-line code-line">定义
            <code>bestAction</code>用于存储最高得分的动作序列</li>
        <li data-line="27" class="code-line code-line">初始化因子
            <code>flag</code>为-1或+1.</li>
        <li data-line="28" class="code-line code-line">遍历所有当前局势下所有可能的动作
            <ul>
                <li data-line="29" class="code-line code-line">定义变量
                    <code>newState</code>与
                    <code>newValue</code>为此动作的预期局势与得分</li>
                <li data-line="30" class="code-line code-line">如果
                    <code>maximize == true</code>则取其中的得分最高项，反之取最低得分</li>
                <li data-line="31" class="code-line code-line">两个if是为了保证
                    <code>bestAction</code>中的actions得分相同且均为最优解</li>
            </ul>
        </li>
        <li data-line="32" class="code-line code-line">从
            <code>bestAction</code>中随机选取一个action执行</li>
    </ol>
    <h3 data-line="34" class="code-line code-line" id="public-float-minimaxrecursorstate-state--int-depth--boolean-maximize">public float miniMaxRecursor(State state, int depth, boolean maximize)</h3>
    <p data-line="36" class="code-line code-line">此函数与上一个函数
        <code>decide</code>相似，是抽象出来的递归部分</p>
    <ol>
        <li data-line="38" class="code-line code-line">如果
            <code>computedStates</code>中存在，即已经计算过得分，则直接返回</li>
        <li data-line="39" class="code-line code-line">如果游戏结束或者到达递归最底层，则直接返回当前局面由启发式函数计算的评估分数</li>
        <li data-line="40" class="code-line code-line">与函数
            <code>decide</code>大体相同</li>
        <li data-line="41" class="code-line code-line">最后返回评估分数</li>
    </ol>
    <h3 data-line="43" class="code-line code-line" id="private-float-finalizestate-state--float-value">private float finalize(State state, float value)</h3>
    <p data-line="45" class="code-line code-line">未使用，返回
        <code>value</code>。</p>
    <h2 data-line="47" class="code-line code-line" id="task-2">Task 2</h2>
    <p data-line="49" class="code-line code-line">对下列函数加入
        <code>alpha</code>与
        <code>beta</code>参数，进行
        <eq>
            <span class="katex">
                <span class="katex-mathml">
                    <math>
                        <semantics>
                            <mrow>
                                <mi>α</mi>
                                <mo>−</mo>
                                <mi>β</mi>
                            </mrow>
                            <annotation encoding="application/x-tex">\alpha-\beta</annotation>
                        </semantics>
                    </math>
                </span>
                <span class="katex-html" aria-hidden="true">
                    <span class="strut" style="height:0.69444em;"></span>
                    <span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span>
                    <span class="base">
                        <span class="mord mathit" style="margin-right:0.0037em;">α</span>
                        <span class="mord rule" style="margin-right:0.2222222222222222em;"></span>
                        <span class="mbin">−</span>
                        <span class="mord rule" style="margin-right:0.2222222222222222em;"></span>
                        <span class="mord mathit" style="margin-right:0.05278em;">β</span>
                    </span>
                </span>
            </span>
        </eq>剪枝</p>
    <pre class="hljs"><code><div><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">float</span> <span class="hljs-title">miniMaxRecursor</span><span class="hljs-params">(State state, <span class="hljs-keyword">int</span> depth, <span class="hljs-keyword">boolean</span> maximize, <span class="hljs-keyword">float</span> alpha, <span class="hljs-keyword">float</span> beta)</span> </span>{
    <span class="hljs-comment">// Has this state already been computed?</span>
    <span class="hljs-keyword">if</span> (computedStates.containsKey(state)) 
                <span class="hljs-comment">// Return the stored result</span>
                <span class="hljs-keyword">return</span> computedStates.get(state);
    <span class="hljs-comment">// Is this state done?</span>
    <span class="hljs-keyword">if</span> (state.getStatus() != Status.Ongoing)
                <span class="hljs-comment">// Store and return</span>
                <span class="hljs-keyword">return</span> finalize(state, state.heuristic());
    <span class="hljs-comment">// Have we reached the end of the line?</span>
    <span class="hljs-keyword">if</span> (depth == <span class="hljs-keyword">this</span>.depth)
                <span class="hljs-comment">//Return the heuristic value</span>
                <span class="hljs-keyword">return</span> state.heuristic();
            
    <span class="hljs-comment">// If not, recurse further. Identify the best actions to take.</span>
    <span class="hljs-keyword">float</span> value = maximize ? Float.NEGATIVE_INFINITY : Float.POSITIVE_INFINITY;
    <span class="hljs-keyword">int</span> flag = maximize ? <span class="hljs-number">1</span> : -<span class="hljs-number">1</span>;
    List&lt;Action&gt; test = state.getActions();
    <span class="hljs-keyword">for</span> (Action action : test) {
        <span class="hljs-comment">// Check it. Is it better? If so, keep it.</span>
        <span class="hljs-keyword">try</span> {
            State childState = action.applyTo(state);
            <span class="hljs-keyword">float</span> newValue = <span class="hljs-keyword">this</span>.miniMaxRecursor(childState, depth + <span class="hljs-number">1</span>, !maximize, alpha, beta);
            <span class="hljs-comment">//Record the best value</span>
            <span class="hljs-keyword">if</span> (flag * newValue &gt; flag * value) {
                value = newValue;
                <span class="hljs-comment">//alpha-beta cut</span>
                <span class="hljs-keyword">if</span> (maximize &amp;&amp; value &gt; alpha) {
                    <span class="hljs-keyword">if</span> (value &gt; beta)
                        <span class="hljs-keyword">return</span> finalize(state, value);
                    alpha = value;
                } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (!maximize &amp;&amp; value &lt; beta) {
                    <span class="hljs-keyword">if</span> (value &lt; alpha)
                        <span class="hljs-keyword">return</span> finalize(state, value);
                    beta = value;
                }
            }
        } <span class="hljs-keyword">catch</span> (InvalidActionException e) {
            <span class="hljs-comment">//Should not go here</span>
            <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> RuntimeException(<span class="hljs-string">"Invalid action!"</span>);
        }
    }
    <span class="hljs-comment">// Store so we don't have to compute it again.</span>
    <span class="hljs-keyword">return</span> finalize(state, value);
}
</div></code></pre>
    <p data-line="98" class="code-line code-line">在
        <code>Othello</code>中递归深度为2时，加入
        <eq>
            <span class="katex">
                <span class="katex-mathml">
                    <math>
                        <semantics>
                            <mrow>
                                <mi>α</mi>
                                <mo>−</mo>
                                <mi>β</mi>
                            </mrow>
                            <annotation encoding="application/x-tex">\alpha-\beta</annotation>
                        </semantics>
                    </math>
                </span>
                <span class="katex-html" aria-hidden="true">
                    <span class="strut" style="height:0.69444em;"></span>
                    <span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span>
                    <span class="base">
                        <span class="mord mathit" style="margin-right:0.0037em;">α</span>
                        <span class="mord rule" style="margin-right:0.2222222222222222em;"></span>
                        <span class="mbin">−</span>
                        <span class="mord rule" style="margin-right:0.2222222222222222em;"></span>
                        <span class="mord mathit" style="margin-right:0.05278em;">β</span>
                    </span>
                </span>
            </span>
        </eq>剪枝后速度几乎毫无变化。 逐渐加深深度，由于深度不大，所以效果依旧不太明显。
    </p>
    <p data-line="101" class="code-line code-line">最后将
        <code>Othello</code>中递归深度由2改为8</p>
    <ul>
        <li data-line="103" class="code-line code-line">在原有未剪枝的版本，前两步还在2s左右，到第三步就默默的不动了。</li>
        <li data-line="104" class="code-line code-line">在加入
            <eq>
                <span class="katex">
                    <span class="katex-mathml">
                        <math>
                            <semantics>
                                <mrow>
                                    <mi>α</mi>
                                    <mo>−</mo>
                                    <mi>β</mi>
                                </mrow>
                                <annotation encoding="application/x-tex">\alpha-\beta</annotation>
                            </semantics>
                        </math>
                    </span>
                    <span class="katex-html" aria-hidden="true">
                        <span class="strut" style="height:0.69444em;"></span>
                        <span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span>
                        <span class="base">
                            <span class="mord mathit" style="margin-right:0.0037em;">α</span>
                            <span class="mord rule" style="margin-right:0.2222222222222222em;"></span>
                            <span class="mbin">−</span>
                            <span class="mord rule" style="margin-right:0.2222222222222222em;"></span>
                            <span class="mord mathit" style="margin-right:0.05278em;">β</span>
                        </span>
                    </span>
                </span>
            </eq>剪枝后，每一步反应时间大约在1s左右。</li>
    </ul>
    <p data-line="106" class="code-line code-line">可见加入了
        <eq>
            <span class="katex">
                <span class="katex-mathml">
                    <math>
                        <semantics>
                            <mrow>
                                <mi>α</mi>
                                <mo>−</mo>
                                <mi>β</mi>
                            </mrow>
                            <annotation encoding="application/x-tex">\alpha-\beta</annotation>
                        </semantics>
                    </math>
                </span>
                <span class="katex-html" aria-hidden="true">
                    <span class="strut" style="height:0.69444em;"></span>
                    <span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span>
                    <span class="base">
                        <span class="mord mathit" style="margin-right:0.0037em;">α</span>
                        <span class="mord rule" style="margin-right:0.2222222222222222em;"></span>
                        <span class="mbin">−</span>
                        <span class="mord rule" style="margin-right:0.2222222222222222em;"></span>
                        <span class="mord mathit" style="margin-right:0.05278em;">β</span>
                    </span>
                </span>
            </span>
        </eq>剪枝后速度大幅度提升。</p>
    <h3 data-line="108" class="code-line code-line" id="task-3">Task 3</h3>
    <p data-line="110" class="code-line code-line">先简单介绍一下框架基本内容</p>
    <table>
        <thead>
            <tr>
                <th>变量名</th>
                <th>解释</th>
            </tr>
        </thead>
        <tbody>
            <tr>
                <td>dimension</td>
                <td>棋局大小8*8</td>
            </tr>
            <tr>
                <td>move</td>
                <td>轮到哪个角色下棋</td>
            </tr>
            <tr>
                <td>Board</td>
                <td>分为h/v/d1/d2，分别是水平，竖直与两个对角线，在代码中经常分别对应于状态0,1,2,3.</td>
            </tr>
            <tr>
                <td>getLines</td>
                <td>得到四个方向的棋子,按照上面的顺序存在lines[]中</td>
            </tr>
            <tr>
                <td>棋盘表示</td>
                <td>8*8棋盘每个地方用2bits存储,共65536种情况,00-空,01-墙,10-P1,11-P2</td>
            </tr>
        </tbody>
    </table>
    <h4 data-line="119" class="code-line code-line" id="heuristic">原有
        <code>heuristic</code>函数</h4>
    <pre class="hljs"><code><div><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">float</span> <span class="hljs-title">heuristic</span><span class="hljs-params">()</span> </span>{
    Status s = <span class="hljs-keyword">this</span>.getStatus();
    <span class="hljs-keyword">int</span> winconstant = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">switch</span> (s) {
    <span class="hljs-keyword">case</span> PlayerOneWon:
        winconstant = <span class="hljs-number">5000</span>;
        <span class="hljs-keyword">break</span>;
    <span class="hljs-keyword">case</span> PlayerTwoWon:
        winconstant = -<span class="hljs-number">5000</span>;
        <span class="hljs-keyword">break</span>;
    <span class="hljs-keyword">default</span>:
        winconstant = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">break</span>;
    }
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.pieceDifferential() +
        <span class="hljs-number">8</span> * <span class="hljs-keyword">this</span>.moveDifferential() +
        <span class="hljs-number">300</span> * <span class="hljs-keyword">this</span>.cornerDifferential() +
        <span class="hljs-number">1</span> * <span class="hljs-keyword">this</span>.stabilityDifferential() + 
        winconstant;
}
</div></code></pre>
    <p data-line="143" class="code-line code-line">其中
        <code>winconstant</code>是得分，在这里以玩家A举例，B同理。</p>
    <ul>
        <li data-line="145" class="code-line code-line">如果A能赢则给5000分的分值</li>
        <li data-line="146" class="code-line code-line">已有多少个棋子的差值，分值1分</li>
        <li data-line="147" class="code-line code-line">有多少个可动点的差值，分值8分</li>
        <li data-line="148" class="code-line code-line">有多少个顶角点的差值，分值300分(顶角点绝对不会被翻转，而且变相相当于两边与一个对角线钦定为你的颜色)</li>
        <li data-line="149" class="code-line code-line">有多少个可翻转棋子的差值(在水平竖直与两个对角线四个方向，能翻转的棋子数的差值)，分值1分</li>
    </ul>
    <p data-line="151" class="code-line code-line">其中，他将棋盘分为水平，竖直与两个对角线，一个四个方向计分并累加。</p>
    <h4 data-line="153" class="code-line code-line" id="heuristic">优化后的
        <code>heuristic</code>函数</h4>
    <pre class="hljs"><code><div><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">float</span> <span class="hljs-title">heuristic</span><span class="hljs-params">()</span> </span>{
    Status s = <span class="hljs-keyword">this</span>.getStatus();
    <span class="hljs-keyword">int</span> winconstant = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">switch</span> (s) {
    <span class="hljs-keyword">case</span> PlayerOneWon:
        winconstant = <span class="hljs-number">5000</span>;
        <span class="hljs-keyword">break</span>;
    <span class="hljs-keyword">case</span> PlayerTwoWon:
        winconstant = -<span class="hljs-number">5000</span>;
        <span class="hljs-keyword">break</span>;
    <span class="hljs-keyword">default</span>:
        winconstant = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">break</span>;
    }
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.pieceDifferential() +
        <span class="hljs-number">8</span> * <span class="hljs-keyword">this</span>.moveDifferential() +
        <span class="hljs-number">300</span> * <span class="hljs-keyword">this</span>.cornerDifferential() +
        <span class="hljs-number">150</span> * <span class="hljs-keyword">this</span>.fixDifferential() +
        <span class="hljs-number">1</span> * <span class="hljs-keyword">this</span>.stabilityDifferential() -
        <span class="hljs-number">50</span> * <span class="hljs-keyword">this</span>.nextCornerDifferential() +
        <span class="hljs-number">20</span> * <span class="hljs-keyword">this</span>.edgeDifferential() +
        <span class="hljs-number">20</span> * <span class="hljs-keyword">this</span>.centerDifferential() +
        winconstant;
}
</div></code></pre>
    <p data-line="182" class="code-line code-line">主要的改动在于我添加了新的考虑因素，简单介绍一下</p>
    <h5 data-line="184" class="code-line code-line" id="nextcornerdifferential">
        <code>nextCornerDifferential()</code>
    </h5>
    <p data-line="186" class="code-line code-line">这个函数主要考虑了22点，22点的定义是指</p>
    <table>
        <thead>
            <tr>
                <th>.</th>
                <th>.</th>
                <th>.</th>
                <th>.</th>
                <th>.</th>
                <th>.</th>
                <th>.</th>
                <th>.</th>
            </tr>
        </thead>
        <tbody>
            <tr>
                <td>.</td>
                <td>x</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>x</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>x</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>x</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
        </tbody>
    </table>
    <p data-line="197" class="code-line code-line">图中的四个一定要慎重考虑，尽量逼迫对方棋子下在这里， 这样的话就可以将棋下在4个corner处，从而相当于霸占了两个边加一个对角线。 所以我将这四个点给予负分50的权重。
    </p>
    <h5 data-line="201" class="code-line code-line" id="edgedifferential">edgeDifferential()</h5>
    <p data-line="203" class="code-line code-line">这个函数用来计算四条边的棋子数量，因为中间的棋子贴边，相比之下他的比分要高于其他位置，</p>
    <table>
        <thead>
            <tr>
                <th>x</th>
                <th>x</th>
                <th>x</th>
                <th>x</th>
                <th>x</th>
                <th>x</th>
                <th>x</th>
                <th>x</th>
            </tr>
        </thead>
        <tbody>
            <tr>
                <td>x</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>x</td>
            </tr>
            <tr>
                <td>x</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>x</td>
            </tr>
            <tr>
                <td>x</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>x</td>
            </tr>
            <tr>
                <td>x</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>x</td>
            </tr>
            <tr>
                <td>x</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>x</td>
            </tr>
            <tr>
                <td>x</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>x</td>
            </tr>
            <tr>
                <td>x</td>
                <td>x</td>
                <td>x</td>
                <td>x</td>
                <td>x</td>
                <td>x</td>
                <td>x</td>
                <td>x</td>
            </tr>
        </tbody>
    </table>
    <p data-line="215" class="code-line code-line">我将边上的棋子，赋予20的权重</p>
    <h5 data-line="217" class="code-line code-line" id="centerdifferential">centerDifferential</h5>
    <p data-line="219" class="code-line code-line">对中间的棋子赋予20的权重，因为他们可以分割战场</p>
    <table>
        <thead>
            <tr>
                <th>.</th>
                <th>.</th>
                <th>.</th>
                <th>.</th>
                <th>.</th>
                <th>.</th>
                <th>.</th>
                <th>.</th>
            </tr>
        </thead>
        <tbody>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>x</td>
                <td>x</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>x</td>
                <td>x</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
        </tbody>
    </table>
    <p data-line="231" class="code-line code-line">当占据了中间的位置时，可以更方便的打乱对面密集的棋局。</p>
    <h5 data-line="233" class="code-line code-line" id="fixdifferential">fixDifferential</h5>
    <p data-line="235" class="code-line code-line">从四个顶角开始，递归的计算哪些点同顶角一样不可能被翻转了。</p>
    <table>
        <thead>
            <tr>
                <th>x</th>
                <th>
                    <eq>
                        <span class="katex">
                            <span class="katex-mathml">
                                <math>
                                    <semantics>
                                        <mrow>
                                            <mo>→</mo>
                                        </mrow>
                                        <annotation encoding="application/x-tex">\rightarrow</annotation>
                                    </semantics>
                                </math>
                            </span>
                            <span class="katex-html" aria-hidden="true">
                                <span class="strut" style="height:0.36687em;"></span>
                                <span class="strut bottom" style="height:0.36687em;vertical-align:0em;"></span>
                                <span class="base">
                                    <span class="mrel">→</span>
                                </span>
                            </span>
                        </span>
                    </eq>
                </th>
                <th>.</th>
                <th>.</th>
                <th>.</th>
                <th>.</th>
                <th>
                    <eq>
                        <span class="katex">
                            <span class="katex-mathml">
                                <math>
                                    <semantics>
                                        <mrow>
                                            <mo>←</mo>
                                        </mrow>
                                        <annotation encoding="application/x-tex">\leftarrow</annotation>
                                    </semantics>
                                </math>
                            </span>
                            <span class="katex-html" aria-hidden="true">
                                <span class="strut" style="height:0.36687em;"></span>
                                <span class="strut bottom" style="height:0.36687em;vertical-align:0em;"></span>
                                <span class="base">
                                    <span class="mrel">←</span>
                                </span>
                            </span>
                        </span>
                    </eq>
                </th>
                <th>x</th>
            </tr>
        </thead>
        <tbody>
            <tr>
                <td>
                    <eq>
                        <span class="katex">
                            <span class="katex-mathml">
                                <math>
                                    <semantics>
                                        <mrow>
                                            <mo>↓</mo>
                                        </mrow>
                                        <annotation encoding="application/x-tex">\downarrow</annotation>
                                    </semantics>
                                </math>
                            </span>
                            <span class="katex-html" aria-hidden="true">
                                <span class="strut" style="height:0.69444em;"></span>
                                <span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span>
                                <span class="base">
                                    <span class="mrel">↓</span>
                                </span>
                            </span>
                        </span>
                    </eq>
                </td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>
                    <eq>
                        <span class="katex">
                            <span class="katex-mathml">
                                <math>
                                    <semantics>
                                        <mrow>
                                            <mo>↓</mo>
                                        </mrow>
                                        <annotation encoding="application/x-tex">\downarrow</annotation>
                                    </semantics>
                                </math>
                            </span>
                            <span class="katex-html" aria-hidden="true">
                                <span class="strut" style="height:0.69444em;"></span>
                                <span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span>
                                <span class="base">
                                    <span class="mrel">↓</span>
                                </span>
                            </span>
                        </span>
                    </eq>
                </td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
            </tr>
            <tr>
                <td>
                    <eq>
                        <span class="katex">
                            <span class="katex-mathml">
                                <math>
                                    <semantics>
                                        <mrow>
                                            <mo>↑</mo>
                                        </mrow>
                                        <annotation encoding="application/x-tex">\uparrow</annotation>
                                    </semantics>
                                </math>
                            </span>
                            <span class="katex-html" aria-hidden="true">
                                <span class="strut" style="height:0.69444em;"></span>
                                <span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span>
                                <span class="base">
                                    <span class="mrel">↑</span>
                                </span>
                            </span>
                        </span>
                    </eq>
                </td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>
                    <eq>
                        <span class="katex">
                            <span class="katex-mathml">
                                <math>
                                    <semantics>
                                        <mrow>
                                            <mo>↑</mo>
                                        </mrow>
                                        <annotation encoding="application/x-tex">\uparrow</annotation>
                                    </semantics>
                                </math>
                            </span>
                            <span class="katex-html" aria-hidden="true">
                                <span class="strut" style="height:0.69444em;"></span>
                                <span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span>
                                <span class="base">
                                    <span class="mrel">↑</span>
                                </span>
                            </span>
                        </span>
                    </eq>
                </td>
            </tr>
            <tr>
                <td>x</td>
                <td>
                    <eq>
                        <span class="katex">
                            <span class="katex-mathml">
                                <math>
                                    <semantics>
                                        <mrow>
                                            <mo>→</mo>
                                        </mrow>
                                        <annotation encoding="application/x-tex">\rightarrow</annotation>
                                    </semantics>
                                </math>
                            </span>
                            <span class="katex-html" aria-hidden="true">
                                <span class="strut" style="height:0.36687em;"></span>
                                <span class="strut bottom" style="height:0.36687em;vertical-align:0em;"></span>
                                <span class="base">
                                    <span class="mrel">→</span>
                                </span>
                            </span>
                        </span>
                    </eq>
                </td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>.</td>
                <td>
                    <eq>
                        <span class="katex">
                            <span class="katex-mathml">
                                <math>
                                    <semantics>
                                        <mrow>
                                            <mo>←</mo>
                                        </mrow>
                                        <annotation encoding="application/x-tex">\leftarrow</annotation>
                                    </semantics>
                                </math>
                            </span>
                            <span class="katex-html" aria-hidden="true">
                                <span class="strut" style="height:0.36687em;"></span>
                                <span class="strut bottom" style="height:0.36687em;vertical-align:0em;"></span>
                                <span class="base">
                                    <span class="mrel">←</span>
                                </span>
                            </span>
                        </span>
                    </eq>
                </td>
                <td>x</td>
            </tr>
        </tbody>
    </table>
    <p data-line="247" class="code-line code-line">由于这些棋子已经确定了他们的颜色不会被改变，所以给与150的权重，因为他们相比与corner战略性小一点</p>
    <h3 data-line="249" class="code-line code-line" id="task-4">Task 4</h3>
    <h4 data-line="251" class="code-line code-line" id="mtdf">MTD(f)算法介绍</h4>
    <p data-line="253" class="code-line code-line">该算法通过使用零大小的搜索窗口多次调用
        <code>AlphaBetaWithMemory</code>来工作。通过放大
        <code>minimax</code>值来搜索。每个
        <code>AlphaBeta</code>调用返回
        <code>minimax</code>值的界限。边界存储在上边界和下边界中，形成围绕该搜索深度的真正最小值的区间。
        <code>Plus</code>和
        <code>minus INFINITY</code>是叶值范围之外的值的简写。当上限和下限碰撞时，找到最小值。</p>
    <p data-line="255" class="code-line code-line">
        <code>MTD(f)</code>仅从零窗口
        <code>alpha-beta</code>搜索获得效率，并使用“良好”边界(变量beta)进行零窗口搜索。通常情况下，
        <code>AlphaBeta</code>会在
        <code>AlphaBeta(root，-INFINITY，+ INFINITY，depth)</code>中使用广泛的搜索窗口进行调用，确保返回值位于
        <code>alpha</code>和
        <code>beta</code>的值之间。在
        <code>MTD(f)</code>中，使用了一个零大小的窗口，这样在每次调用时
        <code>AlphaBeta</code>将会失败或失败，分别返回最小值或最小值的上限或下限。零窗口调用会导致更多的截断，但返回的信息更少 - 仅限于最小最大值。然而，要找到它，
        <code>MTD(f)</code>必须多次调用
        <code>AlphaBeta</code>，才能收敛它。在重复调用
        <code>AlphaBeta</code>时重新搜索部分搜索树的开销会在使用存储和检索其在内存中看到的节点的
        <code>AlphaBeta</code>版本时消失。</p>
    <h4 data-line="257" class="code-line code-line" id="mtdf">MTD(f)伪代码</h4>
    <pre class="hljs"><code><div>function MTDF(root, f, d)
    g := f
    upperBound := +∞
    lowerBound := -∞
    while lowerBound &lt; upperBound
        β := max(g, lowerBound+1)
        g := AlphaBetaWithMemory(root, β-1, β, d)
        if g &lt; β then
            upperBound := g
        else
            lowerBound := g
    return g
</div></code></pre>
    <p data-line="274" class="code-line code-line">其中f为猜测的值，为动作action a的分值，最快的算法收敛，第一次通话可能为0。</p>
    <p data-line="276" class="code-line code-line">d为深度，迭代加深深度优先搜索可以通过多次调用
        <code>MTDF()</code>并增加d来完成，并提供f中最好的先前结果</p>
    <h4 data-line="278" class="code-line code-line" id="mtddecider">MTDDecider类</h4>
    <table>
        <thead>
            <tr>
                <th>Name</th>
                <th>introduction</th>
            </tr>
        </thead>
        <tbody>
            <tr>
                <td>Map&lt;State, SearchNode&gt; transpositionTable</td>
                <td>转置表，减少了多次搜索对于重复情况的开销。</td>
            </tr>
            <tr>
                <td>class ActionValuePaipublic</td>
                <td>存储上一次迭代信息</td>
            </tr>
            <tr>
                <td>Action iterative_deepening(State root)</td>
                <td>限制时间内进行零窗口搜索，根据
                    <code>USE_MTDF</code>选择搜索算法</td>
            </tr>
            <tr>
                <td>int MTDF(State root, int firstGuess, int depth)</td>
                <td>MTDF算法，迭代搜索返回当前局面分值</td>
            </tr>
            <tr>
                <td>int AlphaBetaWithMemory(State state, int alpha, int beta, int depth, int color)</td>
                <td>应用了置换表的
                    <eq>
                        <span class="katex">
                            <span class="katex-mathml">
                                <math>
                                    <semantics>
                                        <mrow>
                                            <mi>α</mi>
                                            <mo>−</mo>
                                            <mi>β</mi>
                                        </mrow>
                                        <annotation encoding="application/x-tex">\alpha - \beta</annotation>
                                    </semantics>
                                </math>
                            </span>
                            <span class="katex-html" aria-hidden="true">
                                <span class="strut" style="height:0.69444em;"></span>
                                <span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span>
                                <span class="base">
                                    <span class="mord mathit" style="margin-right:0.0037em;">α</span>
                                    <span class="mord rule" style="margin-right:0.2222222222222222em;"></span>
                                    <span class="mbin">−</span>
                                    <span class="mord rule" style="margin-right:0.2222222222222222em;"></span>
                                    <span class="mord mathit" style="margin-right:0.05278em;">β</span>
                                </span>
                            </span>
                        </span>
                    </eq>剪枝算法，将已搜索的节点存储在置换表中，如果深度&gt;4,则分为depth与depth-2进行搜索</td>
            </tr>
        </tbody>
    </table>
    <h4 data-line="288" class="code-line code-line" id="mtdminimax">MTD与MiniMax对比</h4>
    <h5 data-line="290" class="code-line code-line" id="">共同点</h5>
    <p data-line="292" class="code-line code-line">MTD是基于MiniMax的改进算法，保留了极大极小值与深度限制的部分</p>
    <h5 data-line="294" class="code-line code-line" id="">不同点</h5>
    <p data-line="296" class="code-line code-line">MTD在MiniMax的基础上，引入了置换表技术，减少了重复计算带来的开销，并且增加了AlphaBeta剪枝</p>

</body>

</html>